temporalising unique characterisability and learnability
Temporalising Unique Characterisability and Learnability of Ontology-Mediated Queries
Jung, Jean Christoph, Ryzhikov, Vladislav, Wolter, Frank, Zakharyaschev, Michael
Temporal ontology-mediated query answering provides a framework for accessing temporal data using background knowledge in the form of a logical theory, often called an ontology. Within this framework, queries are usually constructed by combining a domain query language such as conjunctive queries (CQs) with linear temporal logic ( LTL) operators. Ontologies range from pure description logic (DL) ontologies [11, 16], which hold at all timepoints, to suitable combinations of DLs with LTL [7, 9, 28, 10, 48]. On the query side, LTL is combined with domain queries formulated usually as conjunctive queries (CQs). To ensure good semantic and computational properties, one often restricts the use of LTL operators to monotone operators and the domain queries to acyclic CQs such as the class ELIQ of CQs that are equivalent to ELI-queries. On the ontology side, the most popular languages are based on the DL-Lite family of DLs, which underpins the OWL2 DL profile of the W3C standard for ontology-based data access [17, 6]. Our aim in this paper is (i) to find out in how far temporal queries can be (polynomially) characterised using temporal data instances if ontologies encoding background knowledge are present and (ii) to apply the results to study the (polynomial) learnability of temporal queries in Angluin's framework of exact learning [4]. Investigating the computation, size, and shape of unique characterisations of queries by data examples contributes to the query-by-example paradigm in databases [37] as the data examples can be naturally used to illustrate, explain, and construct queries. Unique characterisations also provide a'non-procedural' necessary condition for (polynomial time) exact learnability using membership queries, where membership queries to the oracle take the form'does O,D |= q